\section{Conclusions and open questions}\label{s:conc}

There is a recent surge of proof-of-stake (PoS) based blockchain projects that take a "representative democracy" approach, thereby letting token holders vote for the validator candidates that they trust, and automatically selecting a committee with $k$ of the most trusted candidates. However, the design choices behind these \emph{validator selection protocols} are varied, and formal justifications are scarce. 
%
We present the first social choice analysis for the electoral system of a validator selection protocol, namely for Nominated Proof-of-Stake (NPoS), used by Polkadot and Kusama. 
%
Starting from first principles and in the pursuit of security and decentralization, we formalize the problem in terms of proportional justified representation (PJR) and the maximin support objective, two criteria recently introduced in the literature of proportional representation.
With the problem definition at hand, we show that current election rules either perform poorly in terms of security, or are too slow to be compatible with the blockchain architecture. We then propose $\phragmms$, the first rule to provide formal guarantees on both criteria and be implementable on a blockchain network. 

We propose the adaptation of committee election rules as verifiable computing schemes. Indeed, this adaptation proves to be key for the implementation of the $\phragmms$ rule in the Polkadot network. 
We remark that our proposed verification process (Theorem~\ref{thm:315guarantee}) is linear in the size of the input, and leave it as an open challenge to find an election rule that achieves a constant-factor approximation guarantee for maximin support verifiably, with a verification runtime sublinear in the number of voters.

We present the first approximability analysis for a Phragm\'{e}n objective: we show that the maximin support objective can be approximated within a factor of 2, but not within a factor of $1.2-\eps$ for any $\eps>0$ unless P=NP. This gap between approximability and hardness awaits to be closed in future work. 
Similarly, it remains open to establish whether the approximation factors we proved for $\MMS$ and $\phragmms$ ($2$ and $3.15$ respectively) are tight.

We highlight that our approximation analyses are based on network flow theory, a promising tool that is not widely used in the literature of committee election rules. 
Similarly, we leverage Phragm\'{e}n's notion of load balancing, formalize what it means for a vote distribution over the edges of the approval graph to be balanced, and show how to find a balanced distribution efficiently using new results for parametric flow. We then synthesize the heuristics behind $\phragmen$, $\MMS$ and $\phragmms$ in terms of how well partial solutions are rebalanced in between iterations. 
Further election rules might be analyzed in the future using network flow theory and our definition of balancedness. 
